﻿#pragma once
#include <vector>
#include <functional>
/*
	AvlNode 树基础结构
*/
class AvlNode
{
public:
	AvlNode() : key(0), l(nullptr), r(nullptr), p(nullptr) {}
	AvlNode(int key) : key(key), l(nullptr), r(nullptr), p(nullptr) {}
public:
	int key;
	AvlNode *l;
	AvlNode *r;
	AvlNode *p;
};

/*
	AvlTree 平行二叉树
*/
class AvlTree
{
public:
	AvlTree();
	~AvlTree();
private:
	AvlNode *CreateNode(const int &k);
	void InOrder(AvlNode *t);
	void PreOrder(AvlNode *t);
	void BackOrder(AvlNode *t);
public:
	int height(const AvlNode *root);
	bool insert(const int &k);
	bool remove(const int &k);
	bool remove(AvlNode *t);
	bool empty();
	AvlNode *find(AvlNode *t, const int &k);

	//中序遍历
	void InOrder();

	//前序遍历
	void PreOrder();

	//后序遍历
	void BackOrder();
private:
	AvlNode *root_;
};

class BNode
{
public:
	BNode() = default;
	BNode(int v) : val(v) {}
	int val = 0;
	BNode *l = nullptr;
	BNode *r = nullptr;
	BNode *p = nullptr;
};

class BTree
{
public:
	BTree() = default;
	~BTree() = default;

	void BuildTree(const std::vector<int> &val);
	BNode *CreateNode(int val);
	bool Insert(int val);
	void Clear();
	void PrintPre();
	void PrintPre(BNode *n);
	BNode *m_root = nullptr;
};

/*
	Heap 堆(基于栈)
*/
template<class T, class Compare = std::less<T> >
class Heap
{
public:
	Heap(int s = 100) : maxSize_(s) {}
	Heap(const std::vector<T> &arr, const int &s)
	{
		sourceArr_.reserve(s);
		sourceArr_ = arr;
		maxSize_ = s;

		for (int i = (int)(sourceArr_.size() - 2) / 2; i >= 0; --i)
		{
			SiftDown(i);
		}
	}

	~Heap()
	{
	}

	void push(T &val)
	{
		size_t curSize = sourceArr_.size();
		if (curSize < maxSize_)
		{
			sourceArr_.push_back(val);
			SiftUp(curSize);
		}
	}

	T pop()
	{
		assert(!sourceArr_.empty());

		T t;
		if (sourceArr_.size() == 1)
		{
			t = sourceArr_.back();
			sourceArr_.pop_back();
		}
		else
		{
			std::swap(*(sourceArr_.begin()), *(sourceArr_.end() - 1));
			t = sourceArr_.back();
			sourceArr_.pop_back();
			SiftDown(0);
		}

		return t;
	}

	void clean()
	{
		sourceArr_.clear();
		maxSize_ = 0;
	}

	T &top()
	{
		assert(!sourceArr_.empty());
		return sourceArr_[0];
	}

	std::vector<T> top(int count)
	{
		std::vector<T> v;
		if (sourceArr_.size() < count)
			return v;


		for (int i = 0; i < count; ++i)
		{
			T &t = pop();
			v.push_back(t);
		}
		return v;
	}

	void sort()
	{
		Compare com;
		for (int i = 0; i < sourceArr_.size(); ++i)
		{
			for (int j = i + 1; j < sourceArr_.size(); ++j)
			{
				if (com(sourceArr_[i], sourceArr_[j]))
				{
					std::swap(sourceArr_[i], sourceArr_[j]);
				}
			}
		}
	}

	void SiftUp(int child)
	{
		if (!CheckIdx(child))
			return;

		if (sourceArr_.size() <= 1)
			return;

		Compare com;
		int parent = (child - 1) / 2;
		while (parent >= 0)
		{
			if (com(sourceArr_[child], sourceArr_[parent]))
			{
				std::swap(sourceArr_[child], sourceArr_[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}

	void SiftDown(int root)
	{
		if (!CheckIdx(root))
			return;

		Compare com;
		int parent = root;
		int child = parent * 2 + 1;
		int size = (int)sourceArr_.size();
		while (child < size)
		{
			if (child + 1 < size && com(sourceArr_[child + 1], sourceArr_[child]))
				child++;
			if (com(sourceArr_[child], sourceArr_[parent]))
			{
				std::swap(sourceArr_[child], sourceArr_[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}

	bool CheckIdx(int idx)
	{
		return (idx < 0 && idx >= (int)sourceArr_.size()) ? false : true;
	}

private:
	std::vector<T> sourceArr_;
	int maxSize_;
};